package com.zlk.algorithm.algorithm.dynamicPlan.knapsack073;

import java.io.*;
import java.util.Scanner;

// 有依赖的背包(模版)
// 物品分为两大类：主件和附件
// 主件的购买没有限制，钱够就可以；附件的购买有限制，该附件所归属的主件先购买，才能购买这个附件
// 例如，若想买打印机或扫描仪这样的附件，必须先购买电脑这个主件
// 以下是一些主件及其附件的展示：
// 电脑：打印机，扫描仪 | 书柜：图书 | 书桌：台灯，文具 | 工作椅：无附件
// 每个主件最多有2个附件，并且附件不会再有附件，主件购买后，怎么去选择归属附件完全随意，钱够就可以
// 所有的物品编号都在1~m之间，每个物品有三个信息：价格v、重要度p、归属q
// 价格就是花费，价格 * 重要度 就是收益，归属就是该商品是依附于哪个编号的主件
// 比如一件商品信息为[300,2,6]，花费300，收益600，该商品是6号主件商品的附件
// 再比如一件商品信息[100,4,0]，花费100，收益400，该商品自身是主件(q==0)
// 给定m件商品的信息，给定总钱数n，返回在不违反购买规则的情况下最大的收益
// 测试链接 : https://www.luogu.com.cn/problem/P1064
// 测试链接 : https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
// 数据范围：N<32000，m<60，v<10000，1<=p<=5。
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过
public class Code05_DependentKnapsack {

    private static int MAXN = 32001;
    private static int MAXM = 61;

    static int m,n;//m代表个数 n代表总钱数

    //花费数组
    static int[] cost = new int[MAXM];
    //收益数组
    static int[] val = new int[MAXM];
    //记录附件
    static int follows[][] = new int[MAXM][2];

    public static int[] fans = new int[MAXM];
    public static boolean[] king = new boolean[MAXM];

    public static void clean() {
        for (int i = 1; i <= m; i++) {
            fans[i] = 0;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(bufferedReader);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            m = (int) in.nval;
            clean();
            for (int i = 1, v, p, q; i <= m; i++) {
                in.nextToken(); v = (int) in.nval;
                in.nextToken(); p = (int) in.nval;
                in.nextToken(); q = (int) in.nval;
                cost[i] = v;
                val[i] = v * p;
                king[i] = q == 0;
                if (q != 0) {
                    follows[q][fans[q]++] = i;
                }
            }
            out.println(compute1());
        }
        out.flush();
        out.close();
        bufferedReader.close();
    }

    private static int compute1() {
        //dp 含义 0到i位置选择不超过j的最利润
        //  正常的情况下不考虑依赖 dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-cost[i]]+cost[i])
        // 整体大思路
        //  每次循环取只取主数据，附件数据不取
        //  取到主附件，判断附件的个数，然后采用背包
        //  可能性分析  1、不要主键
        //            2、要主键   不要附件
        //            3、要主键   要附件1
        //            4、要主键   不要附件1 要附件2
        //            5、要主键   要附件 1 2
        //
        int[][] dp =new int[m+1][n+1];
        int pre = 0;
        for (int i = 1; i <= m; i++) {
            if(king[i]){//主件才dp，附件不dp， 因为附件可以根据主键找到
                for (int j = 0; j <= n; j++) {
                    //1、不要主键
                    int p1 = dp[pre][j];
                    int p2=0,p3=0,p4=0,p5=0;
                    int c = cost[i];
                    int v = val[i];
                    //2、要主键
                    if(j>=c){
                        p2 = dp[pre][j-c]+v;
                    }
                    int f1 = fans[i]>0?follows[i][0]:0;
                    int f2 = fans[i]>1?follows[i][1]:0;
                    if(f1>0&&j-c-cost[f1]>=0) {
                        p3 = dp[pre][j - c - cost[f1]] + v + val[f1];
                    }
                    if(f2>0&&j-c-cost[f2]>=0){
                        p4 = dp[pre][j-c-cost[f2]]+v+val[f2];
                    }
                    if(f1>0&&f2>0&&j-c-cost[f2]-cost[f1]>=0){
                        p5 = dp[pre][j-c-cost[f2]-cost[f1]]+v+val[f2]+val[f1];
                    }
                    dp[i][j] =Math.max(Math.max(Math.max(Math.max(p1,p2),p3),p4),p5);
                }
                pre = i;
            }
        }
        return dp[pre][n];
    }

    //空间压缩
    private static int compute2() {
        int[] dp = new int[n+1];
        for (int i = 1, fan1, fan2; i <= m; i++) {
            if (king[i]) {
                for (int j = n; j >=0; j--) {
                    if (j - cost[i] >= 0) {
                        // 可能性2 : 考虑当前主商品，只要主
                        dp[j] = Math.max(dp[j], dp[j - cost[i]] + val[i]);
                    }
                    // fan1 : 如果有附1商品，编号给fan1，如果没有，fan1 == -1
                    // fan2 : 如果有附2商品，编号给fan2，如果没有，fan2 == -1
                    fan1 = fans[i] >= 1 ? follows[i][0] : -1;
                    fan2 = fans[i] >= 2 ? follows[i][1] : -1;
                    if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0) {
                        // 可能性3 : 主 + 附1
                        dp[j] = Math.max(dp[j], dp[j - cost[i] - cost[fan1]] + val[i] + val[fan1]);
                    }
                    if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0) {
                        // 可能性4 : 主 + 附2
                        dp[j] = Math.max(dp[j], dp[j - cost[i] - cost[fan2]] + val[i] + val[fan2]);
                    }
                    if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0) {
                        // 可能性5 : 主 + 附1 + 附2
                        dp[j] = Math.max(dp[j],
                                dp[j - cost[i] - cost[fan1] - cost[fan2]] + val[i] + val[fan1] + val[fan2]);
                    }
                }
            }
        }
        return dp[n];
    }


}
